package pers.qianyu.month_202012.date_20201219;

import java.util.*;

/**
 * 215. 数组中的第K个最大元素
 * https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
 *
 * @author mizzle rain
 * @date 2020-12-19 13:52
 */
public class FindKthLargest {
    // 直接排序
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        int slow = 0, fast = k;
        while (fast < nums.length) {
            fast++;
            slow++;
        }
        return nums[slow];
    }

    // 使用小顶堆
    public int findKthLargest2(int[] nums, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for (int num : nums) {
            q.offer(num);
            if (q.size() > k) {
                q.poll();
            }
        }
        return q.peek();
    }

    // 快速选择算法
    public int findKthLargest3(int[] nums, int k) {
        int n = nums.length - k;
        int left = 0, right = nums.length - 1;
        // 注意这里是 <=
        while (left <= right) {
            int pivot = partition(nums, left, right);
            if (pivot == n) {
                return nums[pivot];
            } else if (pivot > n) {
                right = pivot - 1;
            } else {
                left = pivot + 1;
            }
        }
        return -1;
    }

    private int partition(int[] nums, int left, int right) {
        int mid = ((right - left) >> 1) + left;
        if (nums[left] > nums[right]) {
            swap(nums, left, right);
        }
        if (nums[mid] > nums[right]) {
            swap(nums, mid, right);
        }
        if (nums[left] < nums[mid]) {
            swap(nums, left, mid);
        }
        int pivot = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= pivot) {
                right--;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = pivot;
        return left;
    }

    private void swap(int[] nums, int i, int j) {
        nums[i] = nums[i] ^ nums[j];
        nums[j] = nums[i] ^ nums[j];
        nums[i] = nums[i] ^ nums[j];
    }
}
